package com.vans.practice.alghr;

import java.util.Arrays;

/**
 * @Description: 计数排序
 * @Note: 稳定， k为桶的数量
 * @平均时间复杂度：n + k
 * @空间复杂度： n + k
 * @Author elle
 * @Date 2020/10/14 11:55
 */
public class Count {
    public static void main(String[] args) {
//        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        int[] arr = {140, 6, 7, 3, 20, 17};
        System.out.println(Arrays.toString(sort(arr)));
    }

    private static int[] sort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i: arr) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        //创建数组
        int[] count = new int[max-min + 1];
        for (int i: arr) {
            count[i-min]++;
        }
        int[] result = new int[arr.length];
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                result[index++] = i+min;
                count[i]--;
            }
        }
        return result;
    }

}
